# include <stdio.h>
# include <stdlib.h>

typedef struct BST_node{
	int data;
	struct BST_node * leftChild;
	struct BST_node * rightChild;
} node;

node *insertNode (node *root, int x) {
	node *temp = root;
	node *newNode, *temp1;
	newNode = (node *) malloc (sizeof(struct BST_node));
	newNode -> data = x;
	newNode -> leftChild = NULL;
	newNode -> rightChild = NULL;
	if (temp == NULL)
		root = newNode;
	else {
		while (temp){
			temp1 = temp;
			if (x < temp -> data)
				temp = temp -> leftChild;
			else if ( x > temp -> data)
				temp = temp -> rightChild;
			else {
				printf("Node already exists\n");
				return root;
			}
		}
		if (x < temp1 -> data)
			temp1 -> leftChild = newNode;
		else if ( x > temp1 -> data)
			temp1 -> rightChild = newNode;
	}
	return root;
}

node *nextPredecessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> leftChild) {
		preNode = temp;
		temp = temp -> leftChild;
		while (temp -> rightChild) {
			preNode = temp;
			temp = temp -> rightChild;
		}
		if (preNode -> data != current -> data)
			preNode -> rightChild = temp -> leftChild;
		else
			preNode -> leftChild = temp -> leftChild;
		return temp;
	}
	else
		return NULL;
}

node *nextSuccessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> rightChild) {
		preNode = temp;
		temp = temp -> rightChild;
		while (temp -> leftChild) {
			preNode = temp;
			temp = temp -> leftChild;
		}
		if (preNode -> data != current -> data)
			preNode -> leftChild = temp -> rightChild;
		else
			preNode -> rightChild = temp -> rightChild;
		return temp;
	}
	else
		return nextPredecessor(current);
}

node *deleteNode (node *root, int x) {
	node *temp = root;
	node *nextSucc, *preNode, *temp1;
	
	while (temp){
		temp1 = temp;
		if (x < temp -> data)
			temp = temp -> leftChild;
		else if ( x > temp -> data)
			temp = temp -> rightChild;
		else {
			nextSucc = nextSuccessor(temp);
			if (preNode -> data < temp -> data)
				preNode -> rightChild = nextSucc;
			else
				preNode -> leftChild = nextSucc;
			if (nextSucc) {
				nextSucc -> leftChild = temp -> leftChild;
				nextSucc -> rightChild = temp -> rightChild;
			}
			free (temp);
			break;
		}
		preNode = temp1;
	}
	return root;
}

void searchNode (node *root, int x) {
	node *temp = root;
	
	while (temp){
		if (temp -> data > x)
			temp = temp -> leftChild;
		else if (temp -> data < x)
			temp = temp -> rightChild;
		else if (temp -> data == x) {
			printf ("\nItem %d found\n", x);
			return;
		}
	}
	printf ("\nItem %d not found\n", x);
}

void inOrder (node *root) {
	if (root == NULL)
		return;
	inOrder (root -> leftChild);
	printf("%d\t", root -> data);
	inOrder (root -> rightChild);
}

void preOrder (node *root) {
	if (root == NULL)
		return;
	printf("%d\t", root -> data);
	preOrder (root -> leftChild);
	preOrder (root -> rightChild);
}

void postOrder (node *root) {
	if (root == NULL)
		return;
	postOrder (root -> leftChild);
	postOrder (root -> rightChild);
	printf("%d\t", root -> data);
}

int main() {
	node *root = NULL;
	root = insertNode (root, 3);
	root = insertNode (root, 4);
	root = insertNode (root, 1);
	root = insertNode (root, 2);
	root = insertNode (root, 6);
	root = insertNode (root, 7);
	root = insertNode (root, 5);
	root = insertNode (root, 8);
	root = insertNode (root, 1);
	printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);
	deleteNode (root, 4);
	printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);
	searchNode (root, 7);
	searchNode (root, 9);
	return 0;
}
